A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets. The packets are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Routing devices within a network, often referred to as routers, maintain routing information that describe available routes through the network. Upon receiving an incoming packet, the router examines information within the packet and forwards the packet in accordance with the routing information. In order to maintain an accurate representation of the network, routers exchange routing information in accordance with one or more defined routing protocol, such as an interior gateway protocol (IGP). An interior gateway protocol may be a distance-vector protocol or a link state protocol. With a typical link state routing protocol, the routers exchange information related to available interfaces, metrics and other variables associated with links between network devices. This allows the routers to each construct a complete topology or map of the network. Some examples of link state protocols include the Open Shortest Path First (OSPF) protocol and the Intermediate-System to Intermediate System (IS-IS) protocol.
In Source Packet Routing in Networking (SPRING), an explicitly routed Multiprotocol Label Switching (MPLS) Label Switched Path (LSP) can be considered as an ordered list of adjacency segments. Each adjacency segment is identified by an “Adjacency Segment Identifier”, referred to as an adj-SID. A shortest path MPLS LSP may be a segment that terminates on a node and is called “Node Segment Identifier” or node-SID. Segment routing extensions for ISIS and OSPF protocols specify how a router advertises adj-SIDs or node-SIDs. For MPLS data plane, an adj-SID may simply be an MPLS label. Anode that desires to explicitly route a packet can attach a stack of MPLS labels to that packet, each label representing an adj-SID or a node-SID. In some instances, it may not be possible to determine a node-protecting backup path for packets with multi-label stacks at the time of installing a route for a one-hop tunnel that is based on an adjacency segment.